using System.Collections;
using System.Collections.Generic;
using UnityEngine;

public static class GridSolver
{
    /// <summary>
    /// <para>This method will place number to the array</para>
    /// <para>First generte weight array by <see cref="GetWeightArray"/>. Then call <see cref="SolvingMapDp"/></para>
    /// </summary>
    public static bool SolvingMap(int[] grid)
    {
        int[][] weight = GetWeightArray(grid);
        return SolvingMapDp(grid, weight, 0, 0);
    }

    /// <summary>
    /// (x, y) is coordinate
    /// </summary>
    /// <returns></returns>
    public static bool SolvingMapDp(int[] grid, int[][] weight, int x, int y)
    {
        if (x >= 9 || y >= 9)
            return true;
        // n is grid's index from coordinate
        int n = x * 9 + y;
        if (grid[n] != 0)
        {
            return SolvingMapDp(grid, weight, x + 1, y) && SolvingMapDp(grid, weight, x, y + 1);
        }

        for (int i = 1; i <= 9; i++)
        {
            int b = 1 << (i - 1);
            if (CanPlaceNumber(grid, weight, n, 1 << (i - 1)))
            {
                grid[n] = i;
                weight[0][n / 9] |= b;
                weight[1][n % 9] |= b;
                weight[2][n / 9 / 3 * 3 + n % 9 / 3] |= b;
                if (SolvingMapDp(grid, weight, x + 1, y) && SolvingMapDp(grid, weight, x, y + 1))
                {
                    return true;
                }
                grid[n] = 0;
                weight[0][n / 9] ^= b;
                weight[1][n % 9] ^= b;
                weight[2][n / 9 / 3 * 3 + n % 9 / 3] ^= b;
            }
        }
        return false;
    }

    /// <summary>
    /// weight array meanings:
    /// <list type="number">
    /// <item><description>weight[0] is the row weight</description></item>
    /// <item><description>weight[1] is the colum weight</description></item>
    /// <item><description>weight[2] is the cell weight</description></item>
    /// </list>
    /// </summary>
    /// <param name="grid"></param>
    /// <returns></returns>
    public static int[][] GetWeightArray(int[] grid)
    {
        int[][] weight = new int[3][]
        {
                new int[9],
                new int[9],
                new int[9]
        };
        for (int i = 0; i < weight.Length; i++)
        {
            for (int j = 0; j < weight[i].Length; j++)
            {
                weight[i][j] = 0;
            }
        }

        int len = (int)Mathf.Pow(grid.Length, 0.5f);

        for (int row = 0; row < len; row++)
        {
            for (int col = 0; col < len; col++)
            {
                int b = 1 << (grid[row * len + col] - 1);
                weight[0][row] |= b;
                weight[1][col] |= b;
                weight[2][row / 3 * 3 + col / 3] |= b;
            }
        }
        return weight;
    }

    /// <param name="n">Index of grid</param>
    /// <param name="b">The bit of the number that will place</param>
    /// <returns></returns>
    public static bool CanPlaceNumber(int[] grid, int[][] weight, int n, int b)
    {
        if (grid[n] != 0)
            return false;
        return ((weight[0][n / 9] & b) + (weight[1][n % 9] & b) + (weight[2][n / 9 / 3 * 3 + n % 9 / 3] & b)) == 0;
    }
}
